package dynamic_programming.intervalDP;

import java.util.Arrays;

/**
 * 相同分数的最大操作数目II - 3040
 */
public class 相同分数的最大操作数目II {

    // 定义一个整型数组用于存储原始数字
    int[] nums;
    // 定义一个二维整型数组用于存储动态规划中的中间结果，避免重复计算
    int[][] memo;

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 2, 3, 4};
        int num = new 相同分数的最大操作数目II().maxOperations(nums);
        System.out.println(num);
    }

    /**
     * 计算使数组中任意两个元素相加等于给定目标值的操作最大次数
     *
     * @param nums 输入的整型数组
     * @return 最大操作次数
     */
    public int maxOperations(int[] nums) {
        // 获取数组长度
        int n = nums.length;
        // 将输入的数组赋值给类成员变量
        this.nums = nums;
        // 初始化记忆化搜索的二维数组，大小为n*n，并填充默认值-1表示未计算
        this.memo = new int[n][n];

        // 初始化结果变量res为0
        int res = 0;
        // 分别尝试以数组两端元素和、首尾元素对的和、以及末尾两个元素的和为目标值进行计算
        res = Math.max(res, helper(0, n - 1, nums[0] + nums[n - 1])); // 使用数组两端的和作为目标
        res = Math.max(res, helper(0, n - 1, nums[0] + nums[1]));      // 使用首尾两个元素之和作为目标
        res = Math.max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1])); // 使用最后两个元素之和作为目标

        // 返回最终的最大操作次数
        return res;
    }

    /**
     * 辅助函数，用于重置记忆化搜索的二维数组
     *
     * @param i      起始索引
     * @param j      结束索引
     * @param target 目标和
     * @return 递归计算的结果
     */
    public int helper(int i, int j, int target) {
        // 遍历数组长度，将当前行的所有元素初始化为-1
        for (int k = 0; k < nums.length; k++) {
            Arrays.fill(memo[k], -1);
        }
        // 调用深度优先搜索函数并返回结果
        return dfs(i, j, target);
    }

    /**
     * 深度优先搜索函数，寻找符合条件的操作次数
     *
     * @param i      当前搜索的起始位置
     * @param j      当前搜索的结束位置
     * @param target 当前搜索的目标和
     * @return 在[i, j]范围内，使得元素对和为target的最大操作次数
     */
    public int dfs(int i, int j, int target) {
        // 如果起始位置大于等于结束位置，说明没有更多元素可以组合，返回0
        if (i >= j) {
            return 0;
        }
        // 如果当前位置的结果已经计算过，则直接从memo中返回，避免重复计算
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 初始化操作次数为0
        int ans = 0;

        // 检查并更新操作次数：如果数组两端的元素和为目标值，则移除这两个元素后继续搜索
        if (nums[i] + nums[i + 1] == target) {
            ans = Math.max(ans, dfs(i + 2, j, target) + 1);
        }
        // 同理检查末尾两个元素
        if (nums[j - 1] + nums[j] == target) {
            ans = Math.max(ans, dfs(i, j - 2, target) + 1);
        }
        // 检查两端的元素
        if (nums[i] + nums[j] == target) {
            ans = Math.max(ans, dfs(i + 1, j - 1, target) + 1);
        }

        // 将计算结果存入memo中
        memo[i][j] = ans;
        // 返回当前范围内的最大操作次数
        return ans;
    }
}
